package com.leetcode;

import java.util.Scanner;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No69
 * @description 69. x 的平方根
 * @date 2021/1/26 下午4:00
 */
public class No69 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();
        int res = mySqrt(input);
        System.out.println(res);

    }

    public static int mySqrt(int x) {
        if(x <= 1){
            return x;
        }
        int left = 0,right = x;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if(x / mid == mid){
                return mid;
            }else if(x / mid > mid){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return right;
    }

}
